<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>后序遍历</title>
</head>
<body>
    
    <script>
        //1、定义一个二叉树的对象
        function BinaryTree() {
            //S1-节点
            var Node = function(key) {
                this.key = key;
                this.left = null;
                this.right = null;
            }
            //S2-根节点
            var root = null;

            //S4-插入节点
            var insertNode = (node,newNode) => {
                //S4-1-当新节点小于本节点，左边插入；
                if(newNode.key < node.key){
                    if(node.left === null){
                        node.left = newNode;
                    }else{
                        insertNode(node.left, newNode);
                    }
                }else{
                    //S4-2-否则，右边插入；
                    if(node.right === null){
                        node.right = newNode;
                    }else{
                        insertNode(node.right, newNode);
                    }

                }
            }

            //S3-插入
            this.insert = (key) => {
                var newNode = new Node(key);
                if(root === null){
                    root = newNode;
                }else {
                    insertNode(root,newNode);
                }
            }
            //S5-1- 中序遍历实现
            var inOrderTraverseNode = (node, callback) => {
                if(node != null) {
                    inOrderTraverseNode(node.left,callback);    // 左
                    callback(node.key);                         // 中
                    inOrderTraverseNode(node.right, callback);  // 右
                }
            }

            //S5-中序遍历节点
            this.inOrderTraverse = (callback) => {
                inOrderTraverseNode(root, callback); // 从根节点遍历；
            }

            //S6-1- 前序遍历实现
            var preOrderTraverseNode = (node, callback) => {
                if(node != null) {
                    callback(node.key);                         // 中
                    preOrderTraverseNode(node.left,callback);    // 左
                    preOrderTraverseNode(node.right, callback);  // 右
                }
            }
            // S7- 后序遍历节点
            this.preOrderTraverse = (callback) => {
                preOrderTraverseNode(root, callback); // 从根节点遍历；
            }

            //S6-1- 后序遍历实现
            var postOrderTraverseNode = (node, callback) => {
                if(node != null) {
                    postOrderTraverseNode(node.left,callback);    // 左
                    postOrderTraverseNode(node.right, callback);  // 右
                    callback(node.key);                         // 中
                }
            }
            // S6- 后序遍历节点
            this.postOrderTraverse = (callback) => {
                postOrderTraverseNode(root, callback); // 从根节点遍历；
            }

        }

        var nodes = [8,3,10,1,6,14,4,7,13];
        var binaryTree = new BinaryTree();
        nodes.forEach((key) => {
            binaryTree.insert(key);
        })
        console.log(binaryTree);
    
        var callback = (key) => {
                console.log(key);
        }
        binaryTree.inOrderTraverse(callback);

        binaryTree.preOrderTraverse(callback);

        binaryTree.postOrderTraverse(callback);

    </script>
</body>
</html>